from copy import copy
import time
import math
import sys
import pygame
import Debug
import UAI
import Math
import Helper


class Pathfinding:
    def preMapGeneration(self):
        # Needed input
        self.width         = UAI.options.width
        self.height        = UAI.options.height
        self.density       = UAI.ai.pathfinding.density
        self.objectheight  = 20
        self.objectwidth   = 20
        obsticalslist = UAI.game.getNonMovableObjects()
        # Needed input end
        
        rect = pygame.Rect((0, 0), (self.objectheight, self.objectwidth))
        self.map = []
        for x in range(self.density, self.width, self.density):
            for y in range(self.density, self.height, self.density):
                rect.center = (x,y)
                if rect.collidelist(obsticalslist) == -1:
                    UAI.pathfinding.map.append((x,y))
        if UAI.DEBUG:
            Debug.log('Generated path finding map with ' + str(len(self.map)) + ' points')
            self.drawGrid()

    def getClosestNode(self, pos):
        x, y = pos
        xdiff = x % self.density
        ydiff = y % self.density
        if xdiff > self.density / 2:
            x = x - xdiff + self.density
        else:
            x = x - xdiff
        if ydiff > self.density / 2:
            y = y - ydiff + self.density
        else:
            y = y - ydiff
        return (x, y)
    
    def drawGrid(self):
        for pos in self.map:
            Debug.drawCross(pos, (230,230,230))
    
    def findPath(self, startpos, endpos, method = 'A*'):
        openlist   = []
        closedlist = []
        start = Node(startpos)
        openlist.append(start)
        while openlist:
            current = openlist.pop(0)
            if current.pos == endpos:
                return current
            closedlist.append(current)
            children = self.getChildren(current)
            for child in children:                        
                # First fully working implementation
                '''if not nodeInList(child, openlist) and not nodeInList(child, closedlist):
                    child.setParent(current)
                    child.calculateG()
                    child.calculateH(endpos, method)
                    openlist.append(child)
            self.reorder(openlist)'''
                # Second fully working implementation (little slower, why?)
                '''if nodeInList(child, closedlist):
                    continue
                if nodeInList(child, openlist):
                    child.calculateG()
                    if child.g < current.g:
                        child.setParent(current)
                        child.calculateG()
                        child.calculateH(endpos, method)
                        self.reorder(openlist)
                else:
                    child.setParent(current)
                    child.calculateG()
                    child.calculateH(endpos, method)
                    openlist.append(child)'''
                # Third
                if nodeInList(child, closedlist):
                    continue
                child2 = nodeInList(child, openlist)
                if child2:
                    if child2.g < current.g:
                        child.setParent(child2)
                        child.calculateG()
                        child.calculateH(endpos, method)
                        self.reorder(openlist)
                else:
                    child.setParent(current)
                    child.calculateG()
                    child.calculateH(endpos, method)
                    openlist.append(child)
        return False
    
    def searchForHiding(self, startpos, scarypos):
        openlist   = []
        closedlist = []
        start = Node(startpos)
        openlist.append(start)
        while openlist:
            current = openlist.pop(0)
            if Helper.obsticleInBetweenPos(current.pos, scarypos):
                return current
            closedlist.append(current)
            children = self.getChildren(current)
            for child in children:
                if not nodeInList(child, openlist) and not nodeInList(child, closedlist):
                    child.setParent(current)
                    child.calculateH(scarypos, 'Reversed A*')
                    openlist.append(child)
            self.reorder(openlist)
        return False
    
    def reorder(self, list):      
        return list.sort(self.sorting_function)

    def sorting_function(x, y):
        if x.f < y.f:
            return -1
        else:
            return 0
    sorting_function = staticmethod(sorting_function)

    def getChildren(self, node):
        x, y = node.pos
        neighbours = []
        i = self.density
        if UAI.ai.pathfinding.diagonal:
            childposlist = [(x+i,y), (x,y+i), (x-i,y), (x,y-i), (x+i,y+i), (x-i,y-i), (x+i,y-i), (x-i,y+i)]
        else:
            childposlist = [(x+i,y), (x,y+i), (x-i,y), (x,y-i)]
        for pos in childposlist:
            if pos in self.map:
                node = Node(pos)
                neighbours.append(node)
        return neighbours        
    
def nodeInList(node, list):
    for node2 in list:
        if node.pos == node2.pos:
            return node2
    return False
class Node:
    pos    = (0,0)
    parent = False
    g      = 0
    h      = 0
    f      = 0
    def __init__(self, pos):
        self.pos = pos
        
    def setParent(self, parent):
        self.parent = parent
    
    def calculateG(self):
        if self.parent:
            self.g = int(Math.getDistance(self.pos, self.parent.pos))
            self.g = self.g + self.parent.g
    
    def calculateH(self, endpos, method = 'A*'):
        if method == 'A*':
            if UAI.ai.pathfinding.heuristics == 'Manhattan':
                self.h = UAI.ai.pathfinding.calibrate * Math.normalize(self.pos[0] - endpos[0]) + Math.normalize(self.pos[1] - endpos[1])
            elif UAI.ai.pathfinding.heuristics == 'Euclidean':
                self.h = UAI.ai.pathfinding.calibrate * int(UAI.ai.pathfinding.calibrate * Math.getDistance(self.pos, endpos))
        elif method == 'Reversed A*':
            if UAI.ai.pathfinding.heuristics == 'Manhattan':
                self.h = -UAI.ai.pathfinding.calibrate * Math.normalize(self.pos[0] - endpos[0]) + Math.normalize(self.pos[1] - endpos[1])
            elif UAI.ai.pathfinding.heuristics == 'Euclidean':
                self.h = -UAI.ai.pathfinding.calibrate * int(UAI.ai.pathfinding.calibrate * Math.getDistance(self.pos, endpos))
        elif method == 'Dijkstra':
            self.h = 0
        self.f = self.g + self.h
        if UAI.DEBUG:
            Debug.drawLine(self.pos, self.parent.pos, (255,140,140))
            UAI.window.draw()
            UAI.game.draw()
            pygame.display.flip()